import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Locale;

public class LeetCode784 {
    public static void main(String[] args) {
        System.out.println(letterCasePermutation("3z4"));
    }

    public static List<String> letterCasePermutation(String s) {
        char[] chars = s.toCharArray();

        if (chars.length == 1) {
            if (chars[0] >= 'a' && chars[0] <= 'z') {
                return new ArrayList<>(List.of(s, s.toUpperCase(Locale.ROOT)));
            } else if (chars[0] >= 'A' && chars[0] <= 'Z') {
                return new ArrayList<>(List.of(s, s.toLowerCase(Locale.ROOT)));
            } else {
                return new ArrayList<>(List.of(s));
            }
        }

        List<String> backRes = letterCasePermutation(s.substring(0, s.length() - 1));

        List<String> lastProbably = new ArrayList<>();
        lastProbably.add(String.valueOf(chars[chars.length - 1]));
        if (chars[chars.length - 1] >= 'a' && chars[chars.length - 1] <= 'z') {
            lastProbably.add(String.valueOf((char) (chars[chars.length - 1] - 32)));
        } else if (chars[chars.length - 1] >= 'A' && chars[chars.length - 1] <= 'Z') {
            lastProbably.add(String.valueOf((char) (chars[chars.length - 1] + 32)));
        }

        List<String> res = new ArrayList<>();

        for (String back : backRes) {
            for (String probably : lastProbably) {
                res.add(back + probably);
            }
        }

        return res;
    }


}
